/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class ExamRoom {
	class Node {
		int index;
		Node next;

		public Node(int i) {
			this.index = i;
		}
	}

	Node head;
	int cnt;
	int n;

	public ExamRoom(int N) {
		head = null;
		cnt = 0;
		n = N;
	}

	public int seat() {
		if (cnt == 0) {
			head = new Node(0);
			cnt++;
			return 0;
		} else {
			int maxDistance = 0;
			Node fakeHead = new Node(-head.index);
			Node leftNode = fakeHead;
			fakeHead.next = head;
			Node cur = fakeHead, nxt = fakeHead.next;
			while (nxt != null) {
				int dis = (nxt.index - cur.index) / 2;
				if (maxDistance < dis) {
					dis = maxDistance;
					leftNode = cur;
				}
				cur = nxt;
				nxt = cur.next;
			}
			if (maxDistance < n - 1 - cur.index) {
				leftNode = cur;
				maxDistance = n - 1 - cur.index;
			}
			int targetPos = leftNode.index + maxDistance;
			// 插入到链表中
			Node node = new Node(targetPos);
			node.next = leftNode.next;
			leftNode.next = node;
			cnt++;
			return targetPos;
		}
	}

	public void leave(int p) {
		Node fakeHead = new Node(0);
		fakeHead.next = head;
		Node cur = fakeHead;
		while (cur.next != null) {
			if (cur.next.index == p) {
				cur.next = cur.next.next;
				break;
			}
			cur = cur.next;
		}
		cnt--;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ExamRoom examRoom = new ExamRoom(10);
		System.out.println(examRoom.seat());
		System.out.println(examRoom.seat());
		System.out.println(examRoom.seat());
		System.out.println(examRoom.seat());
		examRoom.leave(4);
		System.out.println(examRoom.seat());

	}

}
